import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-06-22
 * Time: 10:41
 */
public class Solution14 {
    class Solution {
        char[][] path;
        List<List<String>> ret;
        boolean[] checkCol,dig1,dig2;
        int n;

        public List<List<String>> solveNQueens(int n1) {
            n = n1;
            path = new char[n][n];
            ret = new ArrayList<>();
            checkCol = new boolean[n];
            dig1 = new boolean[2*n];
            dig2 = new boolean[2*n];

            //初始化 全部弄为.
            for(int i = 0; i < n; i++) {
                Arrays.fill(path[i],'.');
            }

            dfs(0);

            return ret;
        }

        void dfs(int row) {
            //枚举行
            if(row == n) {
                //添加结果
                List<String> tmp = new ArrayList<>();
                for(int i = 0; i < n; i++) {
                    tmp.add(new String(path[i]));
                }
                ret.add(new ArrayList<>(tmp));
                return;
            }

            for(int col = 0; col  < n; col++) {
                //判断能不能放
                if(checkCol[col] == false && dig1[row - col + n] == false && dig2[row + col] == false) {
                    path[row][col] = 'Q';
                    checkCol[col] = dig1[row-col+n] = dig2[row+col] = true;
                    dfs(row+1);
                    //恢复现场
                    path[row][col] = '.';
                    checkCol[col] = dig1[row-col+n] = dig2[row+col] = false;
                }
            }
        }
    }
}
